package org.yimon.tool.algo.leetcode;

/**
 * @Author ym.gao
 * @Description 环形链表
 * @Date 2024/8/22 下午6:59
 */
public class LeetCode_141_HasCycle {

    public static void main(String[] args) {
        System.out.println(LeetCode_141_HasCycle.hasCycle(new ListNode(1, new ListNode(2))));
    }

    public static boolean hasCycle(ListNode head) {
        //特殊情况判断
        if (head == null || head.next == null) {
            return false;
        }
        //定义快慢指针，从同一个位置出发
        ListNode slow = new ListNode(0, head);
        ListNode fast = new ListNode(0, head);
        while (fast.next != null && fast.next.next != null) {
            if (slow.next == fast.next.next) {//快慢指针相遇，说明存在环
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    private static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
